package com.pojo;


import java.util.ArrayList;
import java.util.Stack;

//二叉树的数据结构
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x){
        this.val = x;
    }
    public TreeNode(){}

     static ArrayList<Integer> list = new ArrayList<Integer>();

    //插入数据
    public static void add(int data,TreeNode tree){
        if (tree == null) {
            tree = new TreeNode();
            tree.val = data;
        }else{
            TreeNode newTree = new TreeNode();
            newTree.val = data;
            TreeNode parent = tree;
            while (true) {
                if (newTree.val < parent.val) {
                    if (parent.left == null) {
                        parent.left = newTree;
                        return;
                    } else {
                        parent = parent.left;
                    }
                } else if (newTree.val > parent.val) {
                    if (parent.right == null){
                        parent.right = newTree;
                        return;
                    } else {
                        parent = parent.right;
                    }
                }
            }
        }
    }

    //先序递归遍历
    public static ArrayList<Integer> preorderTraverse(TreeNode root){
        if(root != null){
            list.add(root.val);
            preorderTraverse(root.left);
            preorderTraverse(root.right);
        }
        return list;
    }

    //先序非递归遍历
    public static ArrayList<Integer> preorderTraverse2(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode newtree = stack.pop();
            list.add(newtree.val);
            if(newtree.right != null)stack.push(newtree.right);
            if(newtree.left != null)stack.push(newtree.left);
        }
        return list;
    }

    //中序递归遍历
    public static ArrayList<Integer> inorderTraverse(TreeNode root){
        if(root != null){
            inorderTraverse(root.left);
            list.add(root.val);
            inorderTraverse(root.right);
        }
        return list;
    }

    //中序非递归遍历
    public static ArrayList<Integer> inorderTraverse2(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }

    //后序递归遍历
    public static ArrayList<Integer> postorderTraverse(TreeNode root){
        if(root != null){
            postorderTraverse(root.left);
            postorderTraverse(root.right);
            list.add(root.val);
        }
        return list;
    }

    //后序非递归遍历
    public static ArrayList<Integer> postorderTraverse2(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = null;
        TreeNode pre = null;
        stack.push(root);
        while(!stack.empty()){
            cur = stack.peek();
            if( (cur.left == null && cur.right == null) || ( pre != null && (pre == cur.left || pre == cur.right) ) ){  //如果当前结点没有孩子结点或者孩子节点都已被访问过
                list.add(cur.val);
                stack.pop();
                pre = cur;
            }else{
                if(cur.right != null){
                    stack.push(cur.right);
                }
                if(cur.left != null){
                    stack.push(cur.left);
                }
            }
        }
        return list;
    }

    //二叉树深度k
    public static int depth(TreeNode root){
        if(root == null)return 0;
        int d1 = depth(root.left);
        int d2 = depth(root.right);
        return (d1>d2?d1:d2)+1;
    }

    //二叉树节点数
    public static int CountNode(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1+CountNode(root.left)+CountNode(root.right);
    }
}
